package com.learn.algorithms.leetcode.medium;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

*/
public class Subsets {

	public List<List<Integer>> subsets(int[] nums) {
		// init remain
		Set<Integer> remain = new HashSet<>();
		for(int item : nums) remain.add(item);
		List<List<Integer>> store = new ArrayList<>();
		store.add(List.of());
		traceBack(new ArrayList<>(), remain, store);
		return store;
	}

	private void traceBack(List<Integer> todo, Set<Integer> remain, List<List<Integer>> store){
		if(!remain.isEmpty()){
			Object[] arr = remain.toArray();
			for(Object item : arr){
				todo.add((Integer)item);
				store.add(new ArrayList<>(todo));
				remain.remove(item);
				traceBack(todo, remain, store);
				todo.remove(item);
			}
			for(Object item : arr) remain.add((Integer)item);
		}
	}
}
